import java.util.Arrays;
public class MyArraylist<E>{

    private Object[] elementData;// 初始数组
    private int usedSize;// 有效大小
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    public MyArraylist() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    public MyArraylist(int initialCapacity) {
        if(initialCapacity >= 0){
            this.elementData = new Object[initialCapacity];
        }else{
            System.out.println("初始化容量不能为负数!");
        }
    }

    public boolean add(E e){
        // 确定一个真正的扩容，预测->扩容
        ensureCapacity(usedSize+1);
        elementData[usedSize++] = e;
        return true;
    }
    public void ensureCapacity(int minCapacity) {// 确定是否要扩容
        // 计算出需要的容量
        int capacity = calculateCapacity(elementData,minCapacity);
        ensureExplicitCapacity(capacity);
    }
    private static int calculateCapacity(Object[] elementData, int minCapacity){
        // 是不是第一次分配大小
        if(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
            return Math.max(minCapacity, 10);
        }
        // 没有的话，就返回真实需要的空间 usedSize+1
        return minCapacity;
    }
    private void ensureExplicitCapacity(int minCapacity){
        if(minCapacity - elementData.length > 0){
            grow(minCapacity);
        }
    }
    private void grow(int minCapacity){
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + oldCapacity>>1;
        if(newCapacity - minCapacity < 0){
            newCapacity = minCapacity;
        }
        if(newCapacity - (Integer.MAX_VALUE-8) > 0){
            newCapacity = Integer.MAX_VALUE;
        }
        elementData = Arrays.copyOf(elementData,newCapacity);
    }



    public void add(int index,E e){
        // 看index是否合理
        rangeCheckForAdd(index);
        ensureCapacity(usedSize+1);
        copy(index,e);
        usedSize++;
    }
    private void copy(int index,E e){
        for (int i = usedSize-1; i >= index; i--) {
            elementData[i+1] = elementData[i];
        }
        elementData[index] = e;
    }
    private void rangeCheckForAdd(int index){
        if(index < 0 || index > this.usedSize){
            throw new IndexOutOfBoundsException("index位置不合法！");
        }
    }

}
